import java.util.Arrays;

/**
 * Take the number 192 and multiply it by each of 1, 2, and 3:
 * 192 × 1 = 192 192 × 2 = 384 192 × 3 = 576 
 * By concatenating each product we get the 1 to 9 pandigital, 192384576. 
 * We will call 192384576 the concatenated product of 192 and (1,2,3) 
 * The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, 
 * giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5). 
 * What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?
 * @author TrinhNX
 * @start_date	: Apr 27, 2015
 * @end_date 	:
 * Conclusion1: 
 * 1. %3 == 0, 4 digit
 * 2. %5 != 0 (x2 = 0 => fail)
 * 3. If 4 digit x1, 2 ( 5001 < 9999)
 * 4. If 3 digit ( 102 < 333)
 * 5. If 2 digit ( 2  2  2 3 -> 12 ->33)
 * 6. If 1 digit (1 2 2 2 2) (6->9)
 */
public class Euler038 {
	//private static final char[] VALID = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	private static final char[] VALID = { '1', '2', '3', '4', '5', '6', '7', '8', '9' };

	public static void main(String[] args) {
		final int MAX = 9999;
		final long start = System.currentTimeMillis();
		System.out.println("Start");
		int value = 0;
		boolean check = true;
		for (int i = MAX; i > 5000; i = i - 3) {
			if (checkPandigital(new int[] { i, i * 2 })) {
				int temp = i * 100000 + i * 2;
				value = (value > temp) ? value : temp;
				check = false;
				break;
			}
		}
		if (check) {
			for (int i = 333; i > 100; i = i - 3) {
				if (checkPandigital(new int[] { i, i * 2, i * 3 })) {
					int temp = i * 1000000 + i * 2 * 1000 + i * 3;
					value = (value > temp) ? value : temp;
					check = false;
					break;
				}
			}
		}

		if (check) {
			for (int i = 33; i > 10; i = i - 3) {
				if (checkPandigital(new int[] { i, i * 2, i * 3, i * 4 })) {
					int temp = i * 10000000 + i * 2 * 1000000 + i * 3 * 1000 + i * 4;
					value = (value > temp) ? value : temp;
					check = false;
					break;
				}
			}
		}

		if (check) {
			for (int i = 9; i > 5; i = i - 3) {
				if (checkPandigital(new int[] { i, i * 2, i * 3, i * 4, i * 5 })) {
					check = false;
					break;
				}
			}
		}
		System.out.println(value);
		System.out.println("End after: " + (System.currentTimeMillis() - start));
	}

	private static boolean checkPandigital(final int[] data) {
		String result = "";
		for (int temp : data) {
			result += Integer.toString(temp);
		}

		if (result.length() != 9)
			return false;
		char[] c_result = result.toCharArray();
		Arrays.sort(c_result);
		return Arrays.equals(VALID, c_result);
	}
}
